COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00011 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a117.tex[106,phy] \today\hfill}
\font\rmn=cmr9

\bigskip
\line{\bf Composition of Algorithms\hfil}

\smallskip
Suppose I want an algorithm to solve the problem of calculating $A\times B+C$,
for numbers $A$, $B$, and~$C$, where $A$ is an integer and $A≥0$. 
A~subalgorithm $S↓1$ may help make the problem easier by making $A$ a smaller
integer:

$(S↓1)\,\cases{\hbox{Decrease $A$ by 1}\cr
\hbox{Increase $C$ by $B$.}\cr}$

\noindent
This subalgorithm changes $A$ and $C$, but doesn't change the answer to the
problem, because $(A-1)\times B+(C+B)=A\times B+C$. Nor does it change the
fact that $A$ is known to be an integer, because if $A$ is an integer, so
is $A-1$.
There is, however, a difficulty with~$S↓1$: it may change $A$ to a negative
number. 
First $A$ will become zero, however, so we make up a new subalgorithm~$S↓2$
with $S↓1$ as a part of it. 

$(S↓2) \quad \hbox{So long as $A>0$, perform $S↓1$.}$

\noindent
Algorithm $S↓2$ can't make
$A$ negative; the condition that $A>0$ guards $S↓1$ from execution when
that could happen. Algorithm $S↓2$ will make $A=0$, after which the answer
to the problem is $0\times B+C=C$, and the problem is solved. It has
a practical difficulty, though, if $A$ is large: it performs $S↓1$ many
times. It takes too much time to be a practical algorithm.

Algorithm $S↓3$ is sometimes helpful in rapidly making the problem small,
by getting $A$ close to zero:

$(S↓3)\,\cases{\hbox{Replace $A$ by half the previous value}\cr
\hbox{Replace $B$ by twice its previous value.}\cr}$

\noindent
It has a difficulty, though: if $A$ is odd, it may make $A$ into a non-integer.
This is readily repaired; combine $S↓3$ with~$S↓1$, using $S↓3$ when it is
safe and $S↓1$ otherwise:

$(S↓4)\quad\hbox{If $A$ is even, perform $S↓3$. Otherwise, perform $S↓1$.}$

\noindent
The condition that $A$ be even guards $S↓3$ against circumstances for which
it wasn't designed. Now $S↓4$ has only the difficulty $S↓1$ had, of making
$A$ negative.

$(S↓5)\quad\hbox{So long as $A>0$, perform $S↓4$.}$

\noindent
This is an algorithm both fast and safe. The condition $A>0$ guards against
$A$ becoming negative. The condition that $A$ be even guards against $A$
becoming a non-integer.
Every time $S↓4$ is performed, $A$ gets smaller, so $A$ eventually reaches
zero. At least every second time $S↓4$ is performed, $A$~is an even number
and is halved, so $A$ reaches zero in a remarkable number of steps. You
should recognize $S↓5$ as the Russian peasant multiplication algorithm,
broken down into its component subalgorithms.

The construction of $S↓5$ exemplifies several of the most useful ways of
building complex algorithms out of simple ones.

\smallskip
\display 25pt:$\bullet$:
Sequential composition; $S↓1$ was formed out of two subalgorithms, to be
done one after the other.

\smallskip
\display 25pt:$\bullet$:
Simultaneous (parallel) composition; the two subalgorithms of $S↓1$ work
independently, so a team of cooperating people or machines could
simultaneously be performing the two.

\smallskip
\display 25pt:$\bullet$:
Conditional composition; $S↓4$ was formed out of two alternative subalgorithms,
with a testable condition that decides which is the appropriate subalgorithm
to use. When a subalgorithm has been selected, it is performed completely
even if the condition that selected it later becomes false.

\smallskip
\display 25pt:$\bullet$:
Indefinite iteration: $S↓5$ was formed by repeatedly performing $S↓4$, always
testing a condition before beginning~$S↓4$. Each time $S↓4$ is started,
it is completed even if the condition that started it later becomes false.
This convention is sometimes confusing to novices, but experience commends it.
Iteration is repetition, and indefinite iteration is repetition where the
number of performances of the  repeated subalgorithm is not predicted in
advance, but determined by the achievement of a goal.

\smallskip
The conditions used in conditional composition and indefinite iteration of
subalgorithms are sometimes called guards. A~{\sl guard\/} is a condition
attached to a subalgorithm to protect it from being used on a problem for
which it was not designed. A~guarded subalgorithm may either have another 
subalgorithm or no action at all as an alternative.

Algorithms built up out of a few simple ones, like addition and testing
for positiveness, by using just sequential and conditional composition
and indefinite iteration, can solve all problems that can be solved by
algorithms at all. There are many other ways, though, to compose algorithms,
either for efficiency or for ease of design.


\bigskip
\parindent0pt
\copyright 1987 Robert W. Floyd

First draft February 24, 1987. 
%revised: February 13, 1987.
%subsequently revised.

\bye